package leetcode;

/**
 * Created by lyk on 2018-6-20.
 * Package name: leetcode
 * Porject name: untitled1
 */
public class DominoandTrominoTiling {
//    无意义的一题。
//
//    https://www.cnblogs.com/grandyang/p/9179556.html
//    这道题是关于多米诺骨牌和三格骨牌的，其中由两个方形格子组成的是多米诺骨牌（音译，即为双格骨牌），
//    而由三个方形格子组成的‘L’型的是三格骨牌，但其实本质还是个拼格子的问题，并没有利用到骨牌酷炫的
//    连倒技能，倒反而更像是俄罗斯方块中的形状。说是有一个2xN大小的棋盘，我们需要用这些多米诺和三格骨
//    牌来将棋盘填满，问有多少种不同的填充方法，结果需要对一个超大数取余。那么根据博主多年的经验，对
//    于这种求极值，并且超大的情况下，只能使用动态规划Dynamic Programming来做，什么暴力递归神马的，等
//    着爆栈吧。
//
//    既然决定了要用DP来做，那么首先就来设计dp数组吧，这里我们就用一个一维的dp数组就行了，其中dp[i]表
//    示填满前i列的不同填法总数对超大数10e^9+7取余后的结果。那么DP解法的难点就是求状态转移方程了，没
//    什么太好的思路的时候，就从最简单的情况开始罗列吧。题目中给了N的范围是[1, 1000]，那么我们来看：
//
//    当N=1时，那么就是一个2x1大小的棋盘，只能放一个多米诺骨牌，只有一种情况。
//
//    当N=2时，那么就是一个2x2大小的棋盘，如下图所示，我们有两种放置方法，可以将两个多米诺骨牌竖着并排放，
//    或者是将其横着并排放。
//
//    当N=3时，那么就是一个3x2大小的棋盘，我们共用五种放置方法，如下图所示。仔细观察这五种情况，我们发现
//    其时时跟上面的情况有联系的。前两种情况其实是N=2的两种情况后面加上了一个竖着的多米诺骨牌，第三种情况
//    其实是N=1的那种情况后面加上了两个平行的横向的多米诺骨牌，后两种情况是N=0（空集）再加上两种三格骨牌
//    对角摆开的情况。
//
//    当N=4时，那么就是一个4x2大小的棋盘，我们共用十一种放置方法，太多了就不一一画出来了，但是其也是由之
//    前的情况组合而成的。首先是N=3的所有情况后面加上一个竖着多米诺骨牌，然后是N=2的所有情况加上两个平行
//    的横向的多米诺骨牌，然后N=1再加上两种三格骨牌对角摆开的情况，然后N=0（空集）再加上两种三格骨牌和一
//    个横向多米诺骨牌组成的情况。
//
//    N=5的情况博主没有再画了，可以参见ZhengKaiWei大神的帖子中的手稿图，很萌～
//
//    根据目前的状况，我们可以总结一个很重要的规律，就是dp[n]是由之前的dp值组成的，其中 dp[n-1] 和 dp[n-2]
//    各自能贡献一种组成方式，而dp[n-3]，一直到dp[0]，都能各自贡献两种组成方式，所以状态转移方程呼之欲出：
//
//    dp[n] = dp[n-1] + dp[n-2] + 2 * (dp[n-3] + ... + dp[0])
//
//            = dp[n-1] + dp[n-3] + dp[n-2] + dp[n-3] + 2 * (dp[n-4] + ... dp[0])
//
//            = dp[n-1] + dp[n-3] + dp[n-1]
//
//            = 2 * dp[n-1] + dp[n-3]
//
//    最后化简后的形式就是最终的状态转移方程了，是不是叼的飞起～
//
//
//

    public int numTilings(int N) {
        int MOD = (int) Math.pow(10, 9) + 7;

        if (N == 1) return 1;
        if (N == 2) return 2;
        if (N == 3) return 5;
        int[] dp = new int[4];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        for (int i = 4; i <= N; ++i) {
            dp[i % 4] = (2 * dp[(i - 1) % 4] % MOD + dp[(i - 3) % 4]) % MOD;
        }
        return dp[N % 4];
    }

    public static void main(String[] args) {
        DominoandTrominoTiling dtt = new DominoandTrominoTiling();
        System.out.println(dtt.numTilings(4));
        System.out.println(dtt.numTilings(10));
        System.out.println(dtt.numTilings(20));
    }

}
